Secret sharing is a technique by which data is transformed into multiple shares so that the original data can be reconstructed by using a certain number of shares or more but none of the original data can be reconstructed by using any number of shares less than the certain number. Some secret sharing schemes impose restrictions on the total number N of shares and the smallest number K (≦N) of shares required for reconstruction and others not.
A typical secret sharing scheme is Shamir's secret sharing scheme (see Non-patent literature 1, for example). In an example of this scheme, shares Si(a)=f(i) (i=1, . . . , N) of a is obtained from a K−1-degree expression f(x), where x is a variable, such that f(0)=a for aεGF(p), where p is a prime, and GF(p) is a finite field of order p. Here, a can be reconstructed from any K different shares because the following relationship holds:
                              a          =                                    f              ⁡                              (                0                )                                      =                                          ∑                                  i                  =                  1                                K                            ⁢                                                          ⁢                                                f                  ⁡                                      (                                          n                      i                                        )                                                  ·                                                      L                    i                                    ⁡                                      (                    0                    )                                                                                      ⁢                                  ⁢                                            L              i                        ⁡                          (              x              )                                =                                    ∏                                                j                  ≠                  i                                ,                                  j                  =                  1                                            K                        ⁢                                                  ⁢                                          x                -                                  n                  j                                                                              n                  i                                -                                  n                  j                                                                                        [                  Formula          ⁢                                          ⁢          1                ]            where n1, . . . , nK are different integers greater than or equal to 1 and less than or equal to N.
One type of secret sharing is a computational secret sharing scheme in which, based on computational safety, no part of original data can be reconstructed from any number of shares less than a certain value (see Non-patent literature 2, for example). In an example of this scheme, information a=(a0, a1, . . . , aK−1) (a0, a1, . . . , aK−1εGF(p)) is encrypted using a common encryption key and shares Ti(c)=f(i) (i=1, . . . , N) of c is obtained from a K−1-degree expression f(x)=c0+c1x+ . . . +cK−1xK−1, where x is an variable, determined by the ciphertext c=(c0, c1, . . . , cK−1) (where c0, c1, . . . , cK−1εGF(p)). The common key is divided separately using a secret sharing scheme such as Shamir's secret sharing scheme. Then, the coefficients c0, c1, . . . , cK−1 of the expression f(x) can be uniquely obtained from K points (ni, f(ni)) (i=1, . . . , K) of the expression f(x), where n1, . . . , nK are different integers greater than or equal to 1 and less than or equal to N. Solutions to c0, c1, . . . , cK−1 can be obtained for the following matrix where c0, c1, . . . , cK−1 are variables:
                              (                                                                      f                  ⁡                                      (                                          n                      1                                        )                                                                                                      ⋮                                                                                      f                  ⁡                                      (                                          n                      K                                        )                                                                                )                =                              (                                                                                n                    1                    0                                                                    ⋯                                                                      n                    1                                          K                      -                      1                                                                                                                    ⋮                                                  ⋱                                                  ⋮                                                                                                  n                    K                    0                                                                    ⋯                                                                      n                    K                                          K                      -                      1                                                                                            )                    ⁢                                    (                                                                                          c                      0                                                                                                            ⋮                                                                                                              c                                              K                        -                        1                                                                                                        )                        .                                              [                  Formula          ⁢                                          ⁢          2                ]            By reconstructing the common key and decrypting c, a can be obtained.
On the other hand, a multiparty computation scheme, which uses secret sharing as an elemental technology, has been proposed. The multiparty computation is a technique in which each computing entity i (i=1, . . . , N) takes an input of information ai and obtains a particular function value Fi(ai, . . . , aN) without revealing the information ai to the other computing entities. In Shamir's secret sharing scheme described above, shares Si(a+b) of a+b and shares Si(ab) of ab can be obtained from shares Si(a), Si(b) of information a, bεGF(p) without revealing inputs into the computing entities (see Non-patent literature 3). That is, multiparty computations of addition and multiplication are possible using Shamir's secret sharing scheme. Note that secret sharing that satisfies the relationship Si(a)+Si(b)=si(a+b) is called additive homomorphic secret sharing.
Another type of secret sharing is linear secret sharing schemes. The linear secret schemes can be defined as secret sharing in which all of the shares of original data aεGF(p) can be represented by aεGF(p) and a linear combination of random numbers on GF(p). It is known that any linear secret sharing scheme can be extended to multiparty computation (see Non-patent literature 4). (see Non-patent literature 4).